

public class code2 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public boolean exist (String[] board, String word) {
        int[][] arr = new int[board.length][board[0].length()];//转为二维数组
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length();j++) {
                arr[i][j] = board[i].charAt(j);
            }
        }
        int[][] vis= new int[board.length][board[0].length()];//标记是否走过
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length();j++) {
                if (arr[i][j]==word.charAt(0)) {
                    if (dfs(arr,word,0,i,j,vis))
                        return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int[][] arr,String word,int k, int m, int n, int[][] vis) {//k代表word遍历到哪了

        //递归出口
        if (k==word.length()) {
            return true;
        }
        if (m<0||m>=arr[0].length||n<0||n>=arr.length||vis[m][n]==0) {
            return false;
        }
        vis[m][n]=1;
        if (arr[m][n]==word.charAt(k)) {
            //k++;不能这样，会有回退的过程
            for (int i = 0; i < 4; i++) {
                dfs(arr,word,k+1,m+dx[i],n+dy[i],vis);
            }
        }
        //回溯
        vis[m][n] = 0;
        return false;
    }

}
